上一篇我們講到RenderObject layout和Widget/Element build的演算法是如何幫助Flutter迅速的處理節點數量龐大的渲染樹，以支援Flutter激進式複合的設計理念。今天就讓我們繼續介紹渲染樹中，其它同樣能夠增進整體效能的演算法和機制。

線性調和(Linear reconciliation)

Reconcilation這個用法據我所知應該也是從React來的，代表的是Virtual DOM改變時，使DOM和Virtual DOM同步的過程。至於在Flutter中，我們指的是當Widget Tree改變後，如何更新它背後對應的Element Tree。首先我們當然不會想要重建整個Element Tree，畢竟它和它背後的RenderObject Tree都相對昂貴，因此我們必須盡可能重複使用原有的Element Tree。也就是說，如何從舊有的Element Tree，經過最少的步驟，最小的改動，達到和新Widget Tree匹配的新Element Tree，就是這一節要探討的問題。

一般而言，在不考慮現實應用的情境下，這類問題會採用tree-diff演算法。但這類型的演算法經常是O(N³)或O(N²logN)，對於widget數量龐大的Flutter來說，顯然不是可行的作法。幸好，在現實應用中，tree的變化絕對不是完全隨機的，而我們也就可以根據最常見的情境來設計我們的演算法。

Flutter最後選擇的策略是，對於每一個Element，只考慮重複利用自己的child，而不去判斷是否能從別的地方挪用別人的child。我們會在下一節看到Flutter如何處理後面這個情境（劇透：GlobalKey）。

也就是說，一般最簡單的tree-diff演算法可能會看到New Tree的藍色部份，就在整棵Old Tree中尋找，然後說「嘿！我只要把藍色部份移過來就好了。」聽起來很美好，但你可以想像在整棵樹中找到這樣剛好匹配的子樹，並不是一件容易的事。而且，在現實應用程式UI中，Element更換parent也不是最常發生的事。因此，Flutter的reconciliation只考慮sibling Element間的重複利用，並採用O(N)的演算法走過每個Element的child list來決定是否重用。

如果你還沒發現的話，這裡描述的其實就是"key是如何影響updateChildren的？"一文中，那個有著六大迴圈的可怕演算法。上次已經非常詳細的講解了它的原始碼，這次就讓我們用幾張精美示意圖來稍微複習一下：

首先來看看新舊children發生了什麼變化：

1. 藍色和黃色位置互換了
2. 多了一個紅色
3. 綠色代表沒變的child

Flutter Reconcilation演算法一開始會試著從頂部和底部開始匹配child，也就是判斷Widget.canUpdate==true，能夠匹配的就直接更新，不重建Element。最後停在第一個不匹配的child，留下中間包含所有不匹配child的部份，但注意中間也有可能包含可以匹配的child。

接下來把old children的中間部份，根據key做成hash table，並把沒有key的捨棄。如此一來，之後就可以用O(1)的時間，查找可以重複利用的child。

最後走過new children的中間部份，根據key查詢hash table，取得可以重複利用的child。這裡新增的紅色child因為沒有匹配，就會建立新的Element。值得注意的是，剩下的綠色child雖然理論上是可以匹配的，但它的舊Element在上一步被捨棄了，因此也必須重建。這就是Flutter Reconcilation演算法，為了達到O(N)的時間複雜度，並針對常見情境最佳化，所做出的小小犧牲。事實上我們也可以想像，兩個有key的widget中間包含一個沒有key的widget，真的是非常少見的情境。

具體上來說，整個演算法是針對以下情境進行了最佳化：

• old children是空的（建立一整個新的list）
• 新舊list完全一樣（可能只有widget設定改變）
• 只在同一個位置發生一個以上widget的新增或刪除
• 新舊list包含帶有相同key的widget

我們可以看到，這些的確是涵蓋了現實應用中最常發生的幾個情境。

樹木手術(Tree surgery)

對樹木動手術，在樹學上指的是把一段樹枝剪下來，嫁接到樹的其它地方。而在數學上，指的是移動整個subtree到不同的parent底下。上一節提到，在現實應用中，subtree更換parent的情境是比較少見的，但也不是完全沒有。例如其中一個應用是Hero Transition，或其它任何在多個頁面重複使用同一個widget的情境。

當然，如果你有看之前的"為什麼要有key？"一文，應該已經知道，我們是透過在這些須要被重複使用的Widget上插入GlobalKey，來保存它的Element, State以及RenderOject。

具體上來說，Element.mount時會檢查它的widget有沒有GlobalKey，如果有的話就將key和Element註冊到一個全域的static map中，以供後續重複使用。當我們把帶有相同GlobalKey的Widget從一個parent移動到另一個parent，就會去查詢GlobalKey map中有沒有對應的Element，如果有的話就可以直接搬過來重用。不僅如此，因為在layout時從parent傳到child的唯一參數就是constraints，如果新parent傳下來的constraints沒有變，搬家的整個RenderObject subtree也就不須要重新進行layout。

常數因子最佳化(Constant-factor optimizations)

從上一篇到這篇的Tree surgery，都是會影響演算法整體時間複雜度的設計，也就是隨著n(widget數量)越大，它們的效果也就越顯著。除此之外，為了能夠更全面的支援激進式複合，Flutter還有一些雖然不會影響時間複雜度，但也相當重要的最佳化機制。

• Child-model agnostic：依常理來說，絕大多數的tree資料結構，要嘛是child保有parent reference，不然就是parent保有children list。然而Flutter卻在RenderObject Tree的實作上，採取了一個相當奇葩的作法，也就是讓不同的RenderObject自己定義parent要怎麼保存child。例如說在RenderStack（和其它使用ContainerRenderObjectMixin的RenderObject）中，children是透過雙向鍊結串列(Doubly LinkedList)來保存的，但在RenderPadding（和其它只有單一child的RenderObject）中，child是直接作為一個成員變數來保存，因此在進行layout時可以更快速的存取和計算。

• RenderParagraph：在各種layout系統中，文字的layout往往是比較麻煩的，因為我們很難事先知道這些文字的字體、粗細、各種修飾，會讓它layout出來之後變成幾行，佔據多少空間。因此在"Flutter Web是怎麼運作的？（上）"一文中，我們看到web上有個layout文字的小技巧。而在"為什麼Flutter的渲染樹這麼複雜？（上）"一文中，我們也看到Android的View base class包含了一些文字相關的屬性，也就是說所有View都有可能須要依賴subtree中文字layout的結果，再去調整自己的layout。幸好，Flutter的激進式複合讓我們可以避免這種問題。我們把最純粹的文字渲染部份獨立出來，打造一個特殊的RenderParagraph來處理，而整個tree上的其它RenderObject，完全不需要在乎它的子樹中，有沒有文字的渲染。再加上我們特殊的layout演算法，只要parent傳下去的constraints沒變，RenderParagraph就不須要重新計算它的文字layout，即使是在進行tree surgery的時候。

• Observable objects：雖然Flutter中絕大部分都是採用響應式的設計，但有時候為了進行一些最佳化，也會採用觀察者模式。舉例來說，Animation就是一個可以被監聽它的變化的物件。這樣的物件可以從我們的Widget tree被傳遞到RenderObject Tree中，讓RederObject直接監聽變化，並根據變化的類型來決定只進行render pipeline的其中一部份。例如當Animation是顏色或透明度的變化時，RenderObject就不需要重新進行layout，只須要進行paint就好了。

這些機制雖然看起不是那麼起眼，但在龐大的widget tree中累積起來，對於渲染效能的影響也是相當可觀的。

結語

我們從最一開始，為了解釋Flutter的渲染樹為什麼有這麼多複雜的演算法和機制，先介紹了Flutter採取激進式複合設計理念的前因後果，接著說明了激進式複合的龐大Widget可能帶來的效能影響，最後介紹了Flutter在三顆渲染樹中，為了增進效能所設計的各種演算法和機制。

其實，這三篇的小系列主要內容都是來自Flutter官方文件中的Inside Fluter - Aggressive Composibility這節。當年剛開始學Flutter的時候，好奇的看了兩三遍，但總是看到一半就因為太難懂而放棄了。後來認真的從頭開始，把渲染樹的各種運作機制搞懂之後，才終於真正瞭解這份文件的內容。因此三篇文章裡面除了官方的內容，也加入了大量我自己的理解和解釋，包含第一篇追根究底的討論，到底為什麼要有Aggressive Composibility。如果你剛好也有看這份官方文件，並且發現我的理解有誤的地方，請務必提出指正。

明天就是最後一篇了，讓我看看會不會作夢夢到什麼好題目吧。